class Solution {//leetcode879——盈利计划
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int MOD=1e9+7;
        int cnt=profit.size();
        vector<vector<int>> dp(n+1,vector<int>(minProfit+1));
        for(int j=0;j<n+1;j++) dp[j][0]=1;

        for(int i=1;i<cnt+1;i++){
            for(int j=n;j>=group[i-1];j--){
                for(int k=minProfit;k>=0;k--){
                    dp[j][k]=dp[j][k];
                    if(j-group[i-1]>=0) dp[j][k]+=dp[j-group[i-1]][max(0,k-profit[i-1])];
                    dp[j][k]%=MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
};